模拟赛题解/2025.9.12 模拟赛

T1-甲虫（beetle）

题面

小 K 和小 N 带领一群朋友去乘船渡海。最初一共有 $n$ 个人，第 $i$ 个人的体力值为 $a_i$。在岸边有一艘船，这艘船的运行规则如下：

• 每次划船时，船上至少要有 $L$ 人用于控制船只行驶，同时船上不能承载超过 $R$ 人。
• 船上所有人必须体力值 $>1$ 才能出发，每使用一次船，船上的人会被运到对岸，此时所有人的体力值减少 （无论往返）。

船可以任意次数往返，你需要判断是否能将所有人运到对岸。

$T\leq30,\sum n\leq5\times10^6,1\leq L\leq R\leq n,1\leq a_i\leq 10^9$。

题解

注意到一共至少需要往返 $\lceil\frac{n-r}{r-l}\rceil$ 次（记为 $x$），而每个人最多可以往返 $\min(x,\lfloor\frac{a_i-1}{2}\rfloor)$ 次。

因此，只需要所有人的往返次数之和大于 $xL$ 次，就一定能到达对岸。

T2-兔子（bunny）

题面

对于一个长度为 $m$ 的数组 $b$，定义一次操作为：选择一个下标 $i$ 满足 $1\leq i\leq m$，一个整数 $j$ 满足 $2^j\leq b_i$，并将 $b_i$ 改为 $b_i\oplus(b_i-2^j)$。令 $f(b)$ 表示对 $b$ 进行任意次操作后，数组所有元素的按位或的最大值。同时定义序列 $b$ 的优美度为让数组 $b$ 的按位或达到 $f(b)$ 所需的最小操作次数。

现在有一个数组 $a$，同时小 K 会给你 $q$ 个询问，每次询问给定 $[l,r]$，求 $a_l\sim a_r$ 构成的子数组的优美度大小，请你回答这个问题。

$T,\sum n,\sum q\leq10^5,0\leq a_i\leq10^9$。

题解

令区间 $[l,r]$ 或值最高位为 $k$，那么最大值为 $2^{k+1}−1$，可以对区间任意一个 $\geq2^k$ 的数，操作两次 $j=k$ 得到。说明操作次数只有 $0,1,2$，$0$ 是容易的，重点在于判断 $1,2$。令或值最低/最高为 $0$ 的位为 $x,y$，那么能操作的数必须满足 $[x,y)$ 位为 $0$，值要 $\geq 2^y$。可以存储 $\log V$ 棵线段树，第 $i$ 棵存每个数 $\geq i$ 位第一个 $1$ 的位置，这样只要区间查询第 $x$ 棵线段树的区间极值是否 $\geq y$。

有可能操作完一个数之后，除了 $[x,y)$ 之外的某些位变成 $0$ 了。但这样的数最多只有 $\log V$ 个，拎出来单独判断，并对其他 $\log V$ 个区间正常 check。

时间复杂度 $O(n\log n\log V)$。

T3-狼（wolf）

题面

C 城正在举行一场盛大的运动会，小 K 和小 Y 作为长跑项目的志愿者，负责记录数据。比赛共进行 $m$ 轮，有 $n$ 人参加。第 $i$ 轮比赛结束后，小 K 和小 Y 会按照以下规则在大小为 $2m\times n$ 的表格 $a$ 中记录成绩：令第 $j$ 个到达终点的运动员编号为 $b_j$，编号为 $j$ 的运动员的排名为 $c_j$，那么 $a_{2i−1,j}=b_j,a_{2i,j}=c_j$。

但赛后小 Y 不慎丢失了表格，幸运的是小 K 记住了 $n$ 个大小为 $2m$ 的可重集 $S_1\sim S_n$，其中 $S_i$ 表示表格第 $i$ 列的所有元素。请根据小 K 的记忆，还原出任意一个满足记录规则的表格，或者报告无解。

$1\leq n\leq10^5,1\leq m\leq7,1\leq S_{i,j}\leq n。$

题解

观察到如果存在 $j\in S_i$，那么必然有 $i\in S_j$，且两两对应。于是我们建立一张 $n$ 个 点的图，将 $i$ 和 $S_i$ 里所有元素连有向边。最后 $i\rightarrow j$ 和 $j\rightarrow i$ 的边数如果不相等则无解，否则我们构造证明有解。

把 $a_{2i−1}$ 和 $a_{2i}$ 看成一组匹配，等价于我们图中需要找到 $m$ 组匹配。每个点的度数为 $2m$，跑一遍欧拉回路之后，每条定向后的边 $(x,y)$，看成一张新图上左部点 $x$ 向右部点 $y$ 的边。

新图用 Hall 定理易证明存在合法匹配，暴力跑网络流是 $O(n\sqrt{n}\cdot m^2)$ 的，但是因为这是 $m$ - 正则二分图，所以单次匹配可以做到 $O(n\log n)$（link），总时间复杂度 $O(nm^2+nm\log n)$。

但实际测出来根号和 $\log$ 并没有明显的效率差异，所以最后一档只给了 12 分，普通流卡卡常或者换种写法大概也是可以过的。

T4-浣熊（raccoon）

题面

小 H 准备为小 K 写一句拼贴诗，诗句均由小写字母组成。现在小 H 手上有两句相同的诗句 $S_1=S_2$。他希望取出 $S_1$ 的一个前缀 $P$ 和 $S_2$ 的一个后缀 $Q$（$P,Q$ 均可以 为空），并把他们拼接成一句新的诗 $S'=P+Q$ 送给小 K。

但并不是每一种组合都是优美的。小 K 有一个喜欢的词 $T$，如果 $S'$ 存在一个子串为 $T$，那么 $S'$ 是优美的。请帮助小 H 统计有多少本质不同的拼贴诗 $S'$，且其是优美的。

定义两句诗 $S,T$ 本质不同当且仅当 $|S|\not=|T|$ 或者存在 $1\leq i\leq min(|S|,|T|)$ 且 $S_i\not=T_i$。

$1\leq|S|\leq5\times10^6,1\leq|T|\leq 2|S|$。

题解

令 $n=|S|$，$m=|T|$。考虑一个弱化的问题：$|T|=1$。此时仅要考虑 $S'$ 本质不同。

对于一个方案 $P=S[1:i],Q=S[j:n]$，只统计 $S[i + 1]\not=S[j]$ 的情况即可做到不重复计数（一个 $S'$ 只被 $|P|$ 最大的方案计算到）。回头看包含 $T$ 的条件，容斥掉 $T$ 在 $P$ 或者 $Q$ 出现的情况，剩下 $T$ 跨越匹配的出现次数。枚举在原串中开始匹配 $T$ 的位置 $p$。

令 $f_i$ 表示从 $S_i$ 开始能匹配 $T$ 的最长长度，那么最终 $P$ 必须为 $S[1:p+f_p−1]$， 否则要么不合法，要么不满足起始条件 $S[i+1]\not=S[j]$。于是我们只需要找到多少个后缀开头能匹配 $T[fp+1:m]$，这个可以通过一遍 $\text{Z}$ 函数解决。

最后有个问题是相同的 $S'$ 可能会匹配多个跨越的 $T$。处理方法是前面枚举 $p$ 的时候钦定其为第一个匹配的开头，容易发现条件是不存在 $q<p$ 和 $T$ 的 $\text{border}\,T'$，使得 $S[q:p−1]=T[1:m−|T'|]$。

对串 $T+S$ 建立失配树并打标记即可，注意一些边界的细节，总时间复杂度 $O(n+m)$。